package  main.java.leetcode.editor.cn;
//2022-07-03 22:54:34
//给你一个正整数 n ，请你找出符合条件的最小整数，其由重新排列 n 中存在的每位数字组成，并且其值大于 n 。如果不存在这样的正整数，则返回 -1 。 
//
// 注意 ，返回的整数应当是一个 32 位整数 ，如果存在满足题意的答案，但不是 32 位整数 ，同样返回 -1 。 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 12
//输出：21
// 
//
// 示例 2： 
//
// 
//输入：n = 21
//输出：-1
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 2³¹ - 1 
// 
// Related Topics 数学 双指针 字符串 👍 271 👎 0

import java.util.ArrayList;
import java.util.List;

class NextGreaterElementIii {
    public static void main(String[] args) {
        //创建该题目的对象方便调用
        Solution solution = new NextGreaterElementIii().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int nextGreaterElement(int x) {
            List<Integer> nums = new ArrayList<>();
            while (x != 0) {
                nums.add(x % 10);
                x /= 10;
            }
            int n = nums.size(), idx = -1;
            for (int i = 0; i < n - 1 && idx == -1; i++) {
                if (nums.get(i + 1) < nums.get(i)) idx = i + 1;
            }
            if (idx == -1) return -1;
            for (int i = 0; i < idx; i++) {
                if (nums.get(i) > nums.get(idx)) {
                    swap(nums, i, idx);
                    break;
                }
            }
            for (int l = 0, r = idx - 1; l < r; l++, r--) swap(nums, l, r);
            long ans = 0;
            for (int i = n - 1; i >= 0; i--) ans = ans * 10 + nums.get(i);
            return ans > Integer.MAX_VALUE ? -1 : (int)ans;
        }
        void swap(List<Integer> nums, int a, int b) {
            int c = nums.get(a);
            nums.set(a, nums.get(b));
            nums.set(b, c);
        }
    }

//leetcode submit region end(Prohibit modification and deletion)

}
